package practice;


import java.util.LinkedList;
import java.util.List;

public class Day25 {

    //最长回文子序列
    //https://leetcode.cn/problems/longest-palindromic-subsequence/
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i == j) {
                        dp[i][j] = 1;
                    }else if(i+1 == j) {
                        dp[i][j] = 2;
                    }else {
                        dp[i][j] = dp[i+1][j-1] + 2;
                    }
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }

    //最长回文字串
    //https://leetcode.cn/problems/longest-palindromic-substring/
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] vis = new boolean[n][n];

        int ret = 0;
        int retI = 0;
        int retJ = 0;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    vis[i][j] = i+1 < j ? vis[i+1][j-1] : true;
                }
                if(vis[i][j] && j-i+1 > ret) {
                    ret = j-i+1;
                    retI = i;
                    retJ = j;
                }
            }
        }
        return s.substring(retI,retJ+1);
    }

    //正则表达式的匹配
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1]; //s的[0,i]区间,p的[0,j]区间
        dp[0][0] = true;
        for(int i = 2; i <= m; i+=2) {
            if(p.charAt(i-1) == '*') {
                dp[0][i] = true;
            }else {
                break;
            }
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-2] || ((p.charAt(j-2) == '.' || p.charAt(j-2) == s.charAt(i-1)) && dp[i-1][j]);
                }else {
                    dp[i][j] = dp[i-1][j-1] && (p.charAt(j-1) == '.' || s.charAt(i-1) == p.charAt(j-1));
                }
            }
        }
        return dp[n][m];
    }
}
